package com.tree.leetcode.array;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
 * @Author frankzsliu
 * @Date 2024/2/3 23:37
 * @Version 1.0
 */
public class SearchMatrix_74 {
    public static void main(String[] args) {
        int[][] matrix = {{10,11,16,20},{1,3,5,7},{23,30,34,60}};
        System.out.println(searchMatrix(matrix, 4));
    }

    /**
     * 从左下角开始找
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length-1;
        int j =0;

        while (i >= 0 && j<matrix[0].length){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] < target){
                j++; //当前列右移
            }else {
                i--;//如果当前节点比target大， 上移一行
            }
        }

        return false;
    }
}
